package com.s11.heap;

import java.util.Arrays;

public class MaxHeap {

	/**
	 * 堆中已经存储的数据个数
	 */
	private int count;

	private Integer[] arr;

	public MaxHeap(int length) {
		this.count = 0;
		this.arr = new Integer[length + 1];
	}

	/**
	 * 堆可以存储的最大数据个数
	 */
	public int getLength() {
		return this.arr.length - 1;
	}
	
	public Integer getTop() {
		if (this.count > 0) {
			return this.arr[1];
		}
		return null;
	}

	public void insert(int data) {
		if (this.count < this.getLength()) {
			// 初始的时候插入空余的位置即可，下标从 1 开始
			this.arr[++this.count] = data;
			int i = this.count;
			// 当不满足父节点 大于等于 叶子节点
			while (i / 2 > 0 && arr[i / 2] < arr[i]) {
				// 自下往上堆化
				this.swap(i / 2, i);
				i /= 2;
			}
		}
	}

	public void removeTop() {
		if (this.count > 0) {
			// 最后一个元素取代堆顶
			this.arr[1] = this.arr[this.count];
			this.arr[this.count] = null;
			this.count--;
			heapify(1, this.count);
		}
	}

	public void copyOf(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			this.arr[i + 1] = arr[i];
		}
		this.count = arr.length;
	}

	public void sort() {
		// i 表示要进行排序的数据个数
		int i = this.count;
		this.buildHeap(i);

		while (i > 1) {
			// 交换位置
			this.swap(1, i);
			i--;
			// 完成堆化 和 顶部元素为最大
			this.heapify(1, i);
		}
	}

	public void clear() {
		for (int i = 1; i < this.arr.length; i++) {
			this.arr[i] = null;
		}
	}

	@Override
	public String toString() {
		return Arrays.toString(this.arr);
	}

	/**
	 * 
	 * @param arr
	 * @param n
	 *            需要堆化元素的个数
	 */
	private void buildHeap(int n) {
		// 每个数据从上到下的堆化
		for (int i = n / 2; i > 0; i--) {
			this.heapify(i, n);
		}
	}

	private void swap(int i, int j) {
		if (i != j) {
			int temp = this.arr[i];
			this.arr[i] = this.arr[j];
			this.arr[j] = temp;
		}
	}

	/**
	 * 对下标为 i 进行从上到下堆化，范围为到 n
	 * 
	 * @param i
	 *            指定下标
	 * @param n
	 *            范围
	 */
	private void heapify(int i, int n) {
		while (true) {
			int maxPosi = i;
			maxPosi = (i * 2 <= n && this.arr[maxPosi] < this.arr[i * 2]) ? i * 2
					: maxPosi;
			maxPosi = (i * 2 + 1 <= n && this.arr[maxPosi] < this.arr[i * 2 + 1]) ? i * 2 + 1
					: maxPosi;
			if (i == maxPosi) {
				break;
			}
			this.swap(maxPosi, i);
			i = maxPosi;
		}
	}

}
